Linear and cyclic distance-three labellings of trees

Abstract

Given a finite or infinite graph G and positive integers ℓ,h1, h2, h3, an L(h1, h2, h3)-labelling of G with span ℓ is a mapping f:V(G)→{0,1,2,...,ℓ} such that, for i=1,2,3 and any u,v∈V(G) at distance i in G, |f(u)-f(v)|≥ hi. A C(h1, h2, h3)-labelling of G with span ℓ is defined similarly by requiring |f(u)-f(v)|ℓ≥ hi instead, where |x|ℓ=min{|x|,ℓ-|x|}. The minimum span of an L(h1,h2,h3)-labelling, or a C(h1, h2, h3)-labelling, of G is denoted by λh1, h2,h3(G)h1,h2,h3(G), respectively. Two related invariants, λ h1, h2,h3(G) h1, h2,h3(G), are defined similarly by requiring further that for every vertex u there exists an interval Iumod(ℓ+1) or modℓ, respectively, such that the neighbours of u ..